package _interview150;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 67. 二进制求和
 */
public class No67 {
    public String addBinary(String a, String b) {
        int m = a.length(), n = b.length();
        boolean flag = false;
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 1; i <= n && i <= m; i++) {
            int curSum = a.charAt(m - i) + b.charAt(n - i) - '0' - '0' + (flag ? 1 : 0);
            flag = curSum / 2 == 1;
            stack.push(curSum % 2);
        }
        for (int i = Math.abs(m - n) - 1; i >= 0; i--) {
            int curSum = (m > n ? a.charAt(i) - '0' : b.charAt(i) - '0') + (flag ? 1 : 0);
            flag = curSum / 2 == 1;
            stack.push(curSum % 2);
        }
        if (flag) stack.push(1);

        StringBuilder ans = new StringBuilder();
        while (!stack.isEmpty()) {
            ans.append(stack.pop());
        }
        return ans.toString();
    }
}
